问题导入:已知一个长度为 n (n≤107)n\ (n≤10^7)n (n≤107) 的序列 aaa,求每一个 maxj=i−k+1i aj (1≤k≤n)max_{j=i-k+1}^i\ a_j\ (1≤k≤n)maxj=i−k+1i aj (1≤k≤n) 。用“暴力”算法的话,时间复杂度为 O(n∗k)O(n*k)O(n∗k),显然是无法接受的,需要优化。
一、单调队列优化
单调队列是一个双端队列,其内元素具有单调性。单调递增用于维护定长区间最小值,单调递减用于维护定长区间最大值。我们以单调递减维护最大值为例,即对于队列内每一个元素 kik_iki ,满足 k1>k2>...>km−1>kmk_1>k_2>...>k_{m-1}>k_mk1 >k2 >...>km−1 >km ,试着优化开头的问题。
首先,队列初始化为空,顺次扫描整个序列 aaa。当扫描到第 iii 个元素时:若队列为空,直接将 aia_iai 加入队列;若队列不为空,判断队列的最后一个元素是否大于 aia_iai ,若大于则将 aia_iai 加入队列末尾,反之删除队列最后一个元素,直到队列为空或队列最后一个元素大于 aia_iai ,将 aia_iai 加入队列末尾。
解释:若队列最后一个元素不大于 aia_iai ,则它肯定不会是区间最大值,可以直接删去,因为如果它是区间最大值,则 aia_iai 肯定也是区间最大值;像这样动态地删去无用数据,以维护队列的单调性,可以减少无效运算,提高算法效率。
输出:如果此时 i≥ki≥ki≥k,则需要输出区间最大值。判断队列第一个元素在数组 aaa 中的下标 jjj,若 j<i−k+1j<i-k+1j<i−k+1,则代表这是之前的区间最大值,需要删去,重复这一步骤直到 j≥i−k+1j≥i-k+1j≥i−k+1,输出 aja_jaj 即数组 aaa 在 [i−k+1,i][i-k+1,i][i−k+1,i] 中的最大值。
时间复杂度分析:由于每一个元素最多入队及出队一次,因此总时间复杂度为 O(n)O(n)O(n) 。实际操作时,队列中可以存储下标 iii 而非 aia_iai ,即维护 ak1>ak2>...>akm−1>akma_{k_1}>a_{k_2}>...>a_{k_{m-1}}>a_{k_m}ak1 >ak2 >...>akm−1 >akm ,这样便于判断队列中元素的下标。
二、C++代码实现
按照上述思路编写代码即可。
本人水平有限,如有疑问,欢迎指正!很水的竞赛(邀请码:5ZsC)